Left Termination of the query pattern reach_in_4(g, g, g, g) w.r.t. the given Prolog program could successfully be proven:



Prolog
  ↳ PrologToPiTRSProof

Clauses:

reach(X, Y, Edges, Not_Visited) :- member(.(X, .(Y, [])), Edges).
reach(X, Z, Edges, Not_Visited) :- ','(member(.(X, .(Y, [])), Edges), ','(member(Y, Not_Visited), ','(delete(Y, Not_Visited, V1), reach(Y, Z, Edges, V1)))).
member(H, .(H, L)).
member(X, .(H, L)) :- member(X, L).
delete(X, .(X, Y), Y).
delete(X, .(H, T1), .(H, T2)) :- delete(X, T1, T2).

Queries:

reach(g,g,g,g).

We use the technique of [30]. With regard to the inferred argument filtering the predicates were used in the following modes:
reach_in: (b,b,b,b)
member_in: (b,b) (f,b)
delete_in: (b,b,f)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog



↳ Prolog
  ↳ PrologToPiTRSProof
PiTRS
      ↳ DependencyPairsProof

Pi-finite rewrite system:
The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)


Using Dependency Pairs [1,30] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

REACH_IN_GGGG(X, Y, Edges, Not_Visited) → U1_GGGG(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
REACH_IN_GGGG(X, Y, Edges, Not_Visited) → MEMBER_IN_GG(.(X, .(Y, [])), Edges)
MEMBER_IN_GG(X, .(H, L)) → U6_GG(X, H, L, member_in_gg(X, L))
MEMBER_IN_GG(X, .(H, L)) → MEMBER_IN_GG(X, L)
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → U2_GGGG(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → MEMBER_IN_AG(.(X, .(Y, [])), Edges)
MEMBER_IN_AG(X, .(H, L)) → U6_AG(X, H, L, member_in_ag(X, L))
MEMBER_IN_AG(X, .(H, L)) → MEMBER_IN_AG(X, L)
U2_GGGG(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_GGGG(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U2_GGGG(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → MEMBER_IN_GG(Y, Not_Visited)
U3_GGGG(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
U3_GGGG(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → DELETE_IN_GGA(Y, Not_Visited, V1)
DELETE_IN_GGA(X, .(H, T1), .(H, T2)) → U7_GGA(X, H, T1, T2, delete_in_gga(X, T1, T2))
DELETE_IN_GGA(X, .(H, T1), .(H, T2)) → DELETE_IN_GGA(X, T1, T2)
U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_GGGG(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → REACH_IN_GGGG(Y, Z, Edges, V1)

The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)
U7_GGA(x1, x2, x3, x4, x5)  =  U7_GGA(x2, x5)
U2_GGGG(x1, x2, x3, x4, x5)  =  U2_GGGG(x2, x3, x4, x5)
U6_AG(x1, x2, x3, x4)  =  U6_AG(x4)
MEMBER_IN_AG(x1, x2)  =  MEMBER_IN_AG(x2)
U6_GG(x1, x2, x3, x4)  =  U6_GG(x4)
MEMBER_IN_GG(x1, x2)  =  MEMBER_IN_GG(x1, x2)
REACH_IN_GGGG(x1, x2, x3, x4)  =  REACH_IN_GGGG(x1, x2, x3, x4)
U4_GGGG(x1, x2, x3, x4, x5, x6)  =  U4_GGGG(x2, x3, x5, x6)
U3_GGGG(x1, x2, x3, x4, x5, x6)  =  U3_GGGG(x2, x3, x4, x5, x6)
U1_GGGG(x1, x2, x3, x4, x5)  =  U1_GGGG(x5)
U5_GGGG(x1, x2, x3, x4, x5)  =  U5_GGGG(x5)
DELETE_IN_GGA(x1, x2, x3)  =  DELETE_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
PiDP
          ↳ DependencyGraphProof

Pi DP problem:
The TRS P consists of the following rules:

REACH_IN_GGGG(X, Y, Edges, Not_Visited) → U1_GGGG(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
REACH_IN_GGGG(X, Y, Edges, Not_Visited) → MEMBER_IN_GG(.(X, .(Y, [])), Edges)
MEMBER_IN_GG(X, .(H, L)) → U6_GG(X, H, L, member_in_gg(X, L))
MEMBER_IN_GG(X, .(H, L)) → MEMBER_IN_GG(X, L)
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → U2_GGGG(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → MEMBER_IN_AG(.(X, .(Y, [])), Edges)
MEMBER_IN_AG(X, .(H, L)) → U6_AG(X, H, L, member_in_ag(X, L))
MEMBER_IN_AG(X, .(H, L)) → MEMBER_IN_AG(X, L)
U2_GGGG(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_GGGG(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U2_GGGG(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → MEMBER_IN_GG(Y, Not_Visited)
U3_GGGG(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
U3_GGGG(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → DELETE_IN_GGA(Y, Not_Visited, V1)
DELETE_IN_GGA(X, .(H, T1), .(H, T2)) → U7_GGA(X, H, T1, T2, delete_in_gga(X, T1, T2))
DELETE_IN_GGA(X, .(H, T1), .(H, T2)) → DELETE_IN_GGA(X, T1, T2)
U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_GGGG(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → REACH_IN_GGGG(Y, Z, Edges, V1)

The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)
U7_GGA(x1, x2, x3, x4, x5)  =  U7_GGA(x2, x5)
U2_GGGG(x1, x2, x3, x4, x5)  =  U2_GGGG(x2, x3, x4, x5)
U6_AG(x1, x2, x3, x4)  =  U6_AG(x4)
MEMBER_IN_AG(x1, x2)  =  MEMBER_IN_AG(x2)
U6_GG(x1, x2, x3, x4)  =  U6_GG(x4)
MEMBER_IN_GG(x1, x2)  =  MEMBER_IN_GG(x1, x2)
REACH_IN_GGGG(x1, x2, x3, x4)  =  REACH_IN_GGGG(x1, x2, x3, x4)
U4_GGGG(x1, x2, x3, x4, x5, x6)  =  U4_GGGG(x2, x3, x5, x6)
U3_GGGG(x1, x2, x3, x4, x5, x6)  =  U3_GGGG(x2, x3, x4, x5, x6)
U1_GGGG(x1, x2, x3, x4, x5)  =  U1_GGGG(x5)
U5_GGGG(x1, x2, x3, x4, x5)  =  U5_GGGG(x5)
DELETE_IN_GGA(x1, x2, x3)  =  DELETE_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains
The approximation of the Dependency Graph [30] contains 4 SCCs with 9 less nodes.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

DELETE_IN_GGA(X, .(H, T1), .(H, T2)) → DELETE_IN_GGA(X, T1, T2)

The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)
DELETE_IN_GGA(x1, x2, x3)  =  DELETE_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

DELETE_IN_GGA(X, .(H, T1), .(H, T2)) → DELETE_IN_GGA(X, T1, T2)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
DELETE_IN_GGA(x1, x2, x3)  =  DELETE_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
QDP
                        ↳ QDPSizeChangeProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

DELETE_IN_GGA(X, .(H, T1)) → DELETE_IN_GGA(X, T1)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

MEMBER_IN_AG(X, .(H, L)) → MEMBER_IN_AG(X, L)

The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)
MEMBER_IN_AG(x1, x2)  =  MEMBER_IN_AG(x2)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

MEMBER_IN_AG(X, .(H, L)) → MEMBER_IN_AG(X, L)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
MEMBER_IN_AG(x1, x2)  =  MEMBER_IN_AG(x2)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
QDP
                        ↳ QDPSizeChangeProof
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

MEMBER_IN_AG(.(H, L)) → MEMBER_IN_AG(L)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
PiDP
                ↳ UsableRulesProof
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

MEMBER_IN_GG(X, .(H, L)) → MEMBER_IN_GG(X, L)

The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)
MEMBER_IN_GG(x1, x2)  =  MEMBER_IN_GG(x1, x2)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

MEMBER_IN_GG(X, .(H, L)) → MEMBER_IN_GG(X, L)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
QDP
                        ↳ QDPSizeChangeProof
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

MEMBER_IN_GG(X, .(H, L)) → MEMBER_IN_GG(X, L)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
PiDP
                ↳ UsableRulesProof

Pi DP problem:
The TRS P consists of the following rules:

U3_GGGG(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → U2_GGGG(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
U2_GGGG(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_GGGG(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → REACH_IN_GGGG(Y, Z, Edges, V1)

The TRS R consists of the following rules:

reach_in_gggg(X, Y, Edges, Not_Visited) → U1_gggg(X, Y, Edges, Not_Visited, member_in_gg(.(X, .(Y, [])), Edges))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))
U1_gggg(X, Y, Edges, Not_Visited, member_out_gg(.(X, .(Y, [])), Edges)) → reach_out_gggg(X, Y, Edges, Not_Visited)
reach_in_gggg(X, Z, Edges, Not_Visited) → U2_gggg(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U2_gggg(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_gggg(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U3_gggg(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_gggg(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U4_gggg(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → U5_gggg(X, Z, Edges, Not_Visited, reach_in_gggg(Y, Z, Edges, V1))
U5_gggg(X, Z, Edges, Not_Visited, reach_out_gggg(Y, Z, Edges, V1)) → reach_out_gggg(X, Z, Edges, Not_Visited)

The argument filtering Pi contains the following mapping:
reach_in_gggg(x1, x2, x3, x4)  =  reach_in_gggg(x1, x2, x3, x4)
U1_gggg(x1, x2, x3, x4, x5)  =  U1_gggg(x5)
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
reach_out_gggg(x1, x2, x3, x4)  =  reach_out_gggg
U2_gggg(x1, x2, x3, x4, x5)  =  U2_gggg(x2, x3, x4, x5)
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
U3_gggg(x1, x2, x3, x4, x5, x6)  =  U3_gggg(x2, x3, x4, x5, x6)
U4_gggg(x1, x2, x3, x4, x5, x6)  =  U4_gggg(x2, x3, x5, x6)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U5_gggg(x1, x2, x3, x4, x5)  =  U5_gggg(x5)
U2_GGGG(x1, x2, x3, x4, x5)  =  U2_GGGG(x2, x3, x4, x5)
REACH_IN_GGGG(x1, x2, x3, x4)  =  REACH_IN_GGGG(x1, x2, x3, x4)
U4_GGGG(x1, x2, x3, x4, x5, x6)  =  U4_GGGG(x2, x3, x5, x6)
U3_GGGG(x1, x2, x3, x4, x5, x6)  =  U3_GGGG(x2, x3, x4, x5, x6)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
PiDP
                    ↳ PiDPToQDPProof

Pi DP problem:
The TRS P consists of the following rules:

U3_GGGG(X, Z, Edges, Not_Visited, Y, member_out_gg(Y, Not_Visited)) → U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_in_gga(Y, Not_Visited, V1))
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → U2_GGGG(X, Z, Edges, Not_Visited, member_in_ag(.(X, .(Y, [])), Edges))
U2_GGGG(X, Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])), Edges)) → U3_GGGG(X, Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
U4_GGGG(X, Z, Edges, Not_Visited, Y, delete_out_gga(Y, Not_Visited, V1)) → REACH_IN_GGGG(Y, Z, Edges, V1)

The TRS R consists of the following rules:

delete_in_gga(X, .(X, Y), Y) → delete_out_gga(X, .(X, Y), Y)
delete_in_gga(X, .(H, T1), .(H, T2)) → U7_gga(X, H, T1, T2, delete_in_gga(X, T1, T2))
member_in_ag(H, .(H, L)) → member_out_ag(H, .(H, L))
member_in_ag(X, .(H, L)) → U6_ag(X, H, L, member_in_ag(X, L))
member_in_gg(H, .(H, L)) → member_out_gg(H, .(H, L))
member_in_gg(X, .(H, L)) → U6_gg(X, H, L, member_in_gg(X, L))
U7_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) → delete_out_gga(X, .(H, T1), .(H, T2))
U6_ag(X, H, L, member_out_ag(X, L)) → member_out_ag(X, .(H, L))
U6_gg(X, H, L, member_out_gg(X, L)) → member_out_gg(X, .(H, L))

The argument filtering Pi contains the following mapping:
member_in_gg(x1, x2)  =  member_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
member_out_gg(x1, x2)  =  member_out_gg
U6_gg(x1, x2, x3, x4)  =  U6_gg(x4)
[]  =  []
member_in_ag(x1, x2)  =  member_in_ag(x2)
member_out_ag(x1, x2)  =  member_out_ag(x1)
U6_ag(x1, x2, x3, x4)  =  U6_ag(x4)
delete_in_gga(x1, x2, x3)  =  delete_in_gga(x1, x2)
delete_out_gga(x1, x2, x3)  =  delete_out_gga(x3)
U7_gga(x1, x2, x3, x4, x5)  =  U7_gga(x2, x5)
U2_GGGG(x1, x2, x3, x4, x5)  =  U2_GGGG(x2, x3, x4, x5)
REACH_IN_GGGG(x1, x2, x3, x4)  =  REACH_IN_GGGG(x1, x2, x3, x4)
U4_GGGG(x1, x2, x3, x4, x5, x6)  =  U4_GGGG(x2, x3, x5, x6)
U3_GGGG(x1, x2, x3, x4, x5, x6)  =  U3_GGGG(x2, x3, x4, x5, x6)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
QDP
                        ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

U4_GGGG(Z, Edges, Y, delete_out_gga(V1)) → REACH_IN_GGGG(Y, Z, Edges, V1)
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → U2_GGGG(Z, Edges, Not_Visited, member_in_ag(Edges))
U3_GGGG(Z, Edges, Not_Visited, Y, member_out_gg) → U4_GGGG(Z, Edges, Y, delete_in_gga(Y, Not_Visited))
U2_GGGG(Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])))) → U3_GGGG(Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))

The TRS R consists of the following rules:

delete_in_gga(X, .(X, Y)) → delete_out_gga(Y)
delete_in_gga(X, .(H, T1)) → U7_gga(H, delete_in_gga(X, T1))
member_in_ag(.(H, L)) → member_out_ag(H)
member_in_ag(.(H, L)) → U6_ag(member_in_ag(L))
member_in_gg(H, .(H, L)) → member_out_gg
member_in_gg(X, .(H, L)) → U6_gg(member_in_gg(X, L))
U7_gga(H, delete_out_gga(T2)) → delete_out_gga(.(H, T2))
U6_ag(member_out_ag(X)) → member_out_ag(X)
U6_gg(member_out_gg) → member_out_gg

The set Q consists of the following terms:

delete_in_gga(x0, x1)
member_in_ag(x0)
member_in_gg(x0, x1)
U7_gga(x0, x1)
U6_ag(x0)
U6_gg(x0)

We have to consider all (P,Q,R)-chains.
We use the reduction pair processor [15].


The following pairs can be oriented strictly and are deleted.


U2_GGGG(Z, Edges, Not_Visited, member_out_ag(.(X, .(Y, [])))) → U3_GGGG(Z, Edges, Not_Visited, Y, member_in_gg(Y, Not_Visited))
The remaining pairs can at least be oriented weakly.

U4_GGGG(Z, Edges, Y, delete_out_gga(V1)) → REACH_IN_GGGG(Y, Z, Edges, V1)
REACH_IN_GGGG(X, Z, Edges, Not_Visited) → U2_GGGG(Z, Edges, Not_Visited, member_in_ag(Edges))
U3_GGGG(Z, Edges, Not_Visited, Y, member_out_gg) → U4_GGGG(Z, Edges, Y, delete_in_gga(Y, Not_Visited))
Used ordering: Polynomial interpretation [25]:

POL(.(x1, x2)) = 1 + x1 + x2   
POL(REACH_IN_GGGG(x1, x2, x3, x4)) = 1 + x4   
POL(U2_GGGG(x1, x2, x3, x4)) = 1 + x3   
POL(U3_GGGG(x1, x2, x3, x4, x5)) = x3   
POL(U4_GGGG(x1, x2, x3, x4)) = x4   
POL(U6_ag(x1)) = x1   
POL(U6_gg(x1)) = 0   
POL(U7_gga(x1, x2)) = 1 + x1 + x2   
POL([]) = 0   
POL(delete_in_gga(x1, x2)) = x2   
POL(delete_out_gga(x1)) = 1 + x1   
POL(member_in_ag(x1)) = x1   
POL(member_in_gg(x1, x2)) = 0   
POL(member_out_ag(x1)) = x1   
POL(member_out_gg) = 0   

The following usable rules [17] were oriented:

delete_in_gga(X, .(X, Y)) → delete_out_gga(Y)
U7_gga(H, delete_out_gga(T2)) → delete_out_gga(.(H, T2))
delete_in_gga(X, .(H, T1)) → U7_gga(H, delete_in_gga(X, T1))



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ QDPOrderProof
QDP
                            ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

REACH_IN_GGGG(X, Z, Edges, Not_Visited) → U2_GGGG(Z, Edges, Not_Visited, member_in_ag(Edges))
U4_GGGG(Z, Edges, Y, delete_out_gga(V1)) → REACH_IN_GGGG(Y, Z, Edges, V1)
U3_GGGG(Z, Edges, Not_Visited, Y, member_out_gg) → U4_GGGG(Z, Edges, Y, delete_in_gga(Y, Not_Visited))

The TRS R consists of the following rules:

delete_in_gga(X, .(X, Y)) → delete_out_gga(Y)
delete_in_gga(X, .(H, T1)) → U7_gga(H, delete_in_gga(X, T1))
member_in_ag(.(H, L)) → member_out_ag(H)
member_in_ag(.(H, L)) → U6_ag(member_in_ag(L))
member_in_gg(H, .(H, L)) → member_out_gg
member_in_gg(X, .(H, L)) → U6_gg(member_in_gg(X, L))
U7_gga(H, delete_out_gga(T2)) → delete_out_gga(.(H, T2))
U6_ag(member_out_ag(X)) → member_out_ag(X)
U6_gg(member_out_gg) → member_out_gg

The set Q consists of the following terms:

delete_in_gga(x0, x1)
member_in_ag(x0)
member_in_gg(x0, x1)
U7_gga(x0, x1)
U6_ag(x0)
U6_gg(x0)

We have to consider all (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 0 SCCs with 3 less nodes.